import java.util.*;

class Solution {
    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode head;

    //使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
    //头插
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head.next;
        ListNode newhead = new ListNode(-1);
        ListNode prev = newhead;
        ListNode ret = head;
        while (cur != null) {
            if (ret.val <= cur.val) {
                cur = cur.next;
                ret = ret.next;
            } else {
                while (prev.next.val > cur.val) {
                    prev = prev.next;
                }
                ret.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            cur = ret.next;
        }
        return head;
    }

    //561. 数组拆分
    //这道题，是两个数字合成一个组，里面找最小的，最小的和次小的，在一个组
    //最小的就是最小的。不用浪费一些大的数字
    public int arrayPairSum(int[] nums) {
      //先给数组排序
      quickSort(nums,0,nums.length-1);
        //利用快排排序
        int min=0;
        for (int i = 0; i <nums.length-1 ; i=i+2) {
            min=min+Math.min(nums[i],nums[i+1]);
        }
        return min;
    }
    public  void quickSort(int [] nums,int start,int end){
       if(start>=end){
           return;
       }
       int pivot=partition(nums,start,end);
       quickSort(nums,start,pivot-1);
       quickSort(nums,pivot+1,end);
    }
    public int  partition(int [] nums,int start,int end){
        int left=start;
        int right=end;
        int pviot=left;
        while(left<right){
            while(left<right&&nums[right]>=nums[pviot]){
                right--;
            }
            while(left<right&&nums[left]<=nums[pviot]){
                left++;
            }
            swap(nums,right,left);
        }
        swap (nums,left,pviot);
        return left;
    }
    public  void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    //143. 重排链表
        public void reorderList(ListNode head) {
           //用线性表将链表存储起来
            List<ListNode>list=new ArrayList<>();
            ListNode cur=head;
            while(cur!=null){
                list.add(cur);
                cur=cur.next;
            }
            int i=0;
            int j=list.size()-1;
            while(i<j){
                list.get(i).next=list.get(j);
                i++;
                if(i==j){
                    break;
                }
                list.get(j).next=list.get(i);
                j--;
            }
            list.get(i).next=null;
        }
}